home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / ingres04.lzh / source / decomp / reduction.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-01-23  |  6.8 KB  |  315 lines
  1. # include    <ingres.h>
  2. # include    <symbol.h>
  3. # include    <aux.h>
  4. # include    <tree.h>
  5. # include    "globs.h"
  6. # include    <sccs.h>
  7.  
  8. SCCSID(@(#)reduction.c    8.1    12/31/84)
  9.  
  10. /*
  11. **    Reduction -- This file contains routines related to the
  12. **    reduction algorithm. The routines are all called by
  13. **    decision().
  14. **
  15. **    Included are:
  16. **
  17. **        algorithm -- groups clauses according to common variables
  18. **
  19. **        buildlist -- build linked list of clauses from a query tree
  20. **
  21. **        construct -- build query trees from link lists of clauses
  22. **
  23. **        order     -- order a linked list of clauses into the prefered
  24. **                execution sequence
  25. */
  26. /*
  27. **    Algorithm - determine whether query is connected or not
  28. **
  29. **    Algorithm takes a linked list of query components
  30. **    and groups them according to the variables involved
  31. **    in each component. If the query is fully interconnected
  32. **    then algorithm returns TRUE else it returns FALSE.
  33. **
  34. **    By definition a constant clause (one involving zero variables)
  35. **    is considered to use all variables. Without this rule,
  36. **    a query with a null target list would always break into
  37. **    two pieces.
  38. **
  39. **    Whether a query is fully connected is independent
  40. **    of whether there are any one variable components
  41. **    or not. This includes the target list. After applying
  42. **    the algorithm, a scan is made to see how many multi-var
  43. **    components are present. If there are two or more multi-var
  44. **    components then the query is disconnected.
  45. **
  46. **    Trace Flags:
  47. **        38
  48. */
  49.  
  50. algorithm(clist, varmap)
  51. struct complist    *clist;
  52. int        varmap;
  53. {
  54.     register struct complist    *chead, *cnext;
  55.     register int            var;
  56.     int                vmap;
  57.     struct complist            *cprev, *cl;
  58.  
  59.     vmap = varmap;
  60.     for (var = 1; vmap; var <<= 1)
  61.     {
  62.         if ((vmap & var) == 0)
  63.             continue;
  64.         vmap &= ~var;    /* remove var */
  65.  
  66.         /* done if query is already a single piece */
  67.         if (clist->nextcomp == 0)
  68.             break;
  69.  
  70.         /* find first component using variable var */
  71.         for (chead = clist; chead; chead = chead->nextcomp)
  72.         {
  73.             if (chead->bitmap == 0 || (chead->bitmap & var))
  74.             {
  75.                 /* this component uses variable var */
  76.  
  77.                 cprev = chead;
  78.         
  79.                 /* look for other components using variable var */
  80.                 for (cnext = chead->nextcomp; cnext; cnext = cnext->nextcomp)
  81.                 {
  82.                     if (cnext->bitmap == 0 || (cnext->bitmap & var))
  83.                     {
  84.         
  85.                         /*
  86.                         ** Found a component. Remove it from "next"
  87.                         ** link and put it with head piece
  88.                         */
  89.         
  90.                         /* remove piece */
  91.                         cprev->nextcomp = cnext->nextcomp;
  92.         
  93.                         /* fix up bit map */
  94.                         chead->bitmap |= cnext->bitmap;
  95.         
  96.                         /* find end of head component */
  97.                         for (cl = chead; cl->linkcomp; cl = cl->linkcomp);
  98.         
  99.                         /* connect with head piece */
  100.                         cl->linkcomp = cnext;
  101.                     }
  102.                     else
  103.                         cprev = cnext;
  104.                 }
  105.             }
  106.         }
  107.     }
  108.  
  109.     /* return whether connected or not connected */
  110.     for (var =0, chead = clist; chead; chead = chead->nextcomp)
  111.         if (bitcnt(chead->bitmap) > 1)
  112.             var++; /* this component involves 2 or more vars */
  113.  
  114.     return (var < 2); /* return TRUE if zero or one component multi-var */
  115. }
  116. /*
  117. **    Buildlist -- Build a component list from a query tree.
  118. **
  119. **    Each ROOT and AND node is treated as a separate component
  120. **    and a linked list is built connecting them. The ROOT node
  121. **    MUST be the first element. This list will later be manipulated
  122. **    by algorithm() to determine the structure of the query.
  123. **
  124. **    Returns:
  125. **        Head of the list
  126. */
  127.  
  128. struct complist *
  129. buildlist(root1, buf)
  130. QTREE    *root1;
  131. char    *buf;
  132. {
  133.     register struct complist    *head, *next;
  134.     register QTREE            *root;
  135.     struct complist            *ret;
  136.     extern char            *need();
  137.  
  138.     ret = (struct complist *) need(buf, 0);
  139.     head = 0;
  140.  
  141.     for (root = root1; root->sym.type != QLEND; root = root->right)
  142.     {
  143.         next = (struct complist *) need(buf, sizeof (*next));
  144.         next->clause = root;
  145.         next->nextcomp = next->linkcomp = 0;
  146.         next->bitmap = root->sym.value.sym_root.lvarm;
  147.  
  148.         if (head)
  149.             head->nextcomp = next;
  150.         head = next;
  151.     }
  152.     return (ret);
  153. }
  154. /*
  155. **  Construct -- construct a tree from a list component
  156. **
  157. **    Construct takes a list head and builds a querytree
  158. **    from the components in the list. If the head component
  159. **    is the ROOT of the original query, then
  160. **    the original ROOT node is reused.
  161. **
  162. */
  163.  
  164. QTREE *
  165. construct(root, listhead, buf)
  166. QTREE        *root;
  167. struct complist    *listhead;
  168. char        *buf;
  169. {
  170.     register QTREE            *ret, *q;
  171.     register struct complist    *clist;
  172.     extern QTREE            *makroot();
  173.  
  174.     clist = listhead;
  175.  
  176.     /* determine ROOT of tree */
  177.     if (root == clist->clause)
  178.     {
  179.         q = root;
  180.         clist = clist->linkcomp;
  181.     }
  182.     else
  183.     {
  184.         q = makroot(buf);
  185.     }
  186.     ret = q;
  187.     for (; clist; clist = clist->linkcomp)
  188.     {
  189.         q->right = clist->clause;
  190.         q = q->right;
  191.     }
  192.  
  193.     q->right = De.de_qle;
  194.  
  195.     mapvar(ret, 1);
  196. #    ifdef xDTR1
  197.     if (tTf(38, 0))
  198.     {
  199.         printf("Construct\n");
  200.         treepr(ret);
  201.     }
  202. #    endif
  203.     return (ret);
  204. }
  205. /*
  206. **  Order -- order a link list set of query components.
  207. **
  208. **    Takes a list of components and orders them:
  209. **        first - disjoint components
  210. **        second - reduction pieces
  211. **        last - the original target list piece
  212. **
  213. **    Return:
  214. **        new head of list
  215. */
  216.  
  217. struct complist *
  218. order(clist, ovlapvar)
  219. struct complist    *clist;
  220. int        ovlapvar;
  221. {
  222.     register struct complist    *cl, *joint, *disjoint;
  223.     struct complist            *xd, *xj, *tlpiece, *ret;
  224.     QTREE                *tmp;
  225.     int                map;
  226.  
  227.     tlpiece = clist;    /* target list piece always first */
  228.     disjoint = joint = 0;
  229.     map = ovlapvar >= 0 ? 1 << ovlapvar : 0;
  230.  
  231.     /* examine each irreducible component for disjointness */
  232.     for (cl = tlpiece->nextcomp; cl; cl = cl->nextcomp)
  233.     {
  234.         if (cl->bitmap & map)
  235.         {
  236.             /* joint piece */
  237.             if (joint == 0)
  238.             {
  239.                 joint = cl;
  240.                 xj = cl;
  241.             }
  242.             else
  243.             {
  244.                 joint->nextcomp = cl;
  245.                 joint = cl;
  246.             }
  247.         }
  248.         else
  249.         {
  250.             /* disjoint piece */
  251.             if (disjoint == 0)
  252.             {
  253.                 disjoint = cl;
  254.                 xd = cl;
  255.             }
  256.             else
  257.             {
  258.                 disjoint->nextcomp = cl;
  259.                 disjoint = cl;
  260.             }
  261.         }
  262.  
  263.     }
  264.     /* we now have all disjoint, joint and tl pieces */
  265.     /* order them in order (1) xd, (2) xj, (3) tlpiece */
  266.  
  267.     ret = tlpiece;
  268.     tlpiece->nextcomp = 0;
  269.  
  270.     if (joint)
  271.     {
  272.         ret = xj;
  273.         joint->nextcomp = tlpiece;
  274.         if ((tlpiece->bitmap & (~map)) == 0)
  275.         {
  276.             /*
  277.             ** This is the special case of the target list
  278.             ** being one (or zero) variable and that variable
  279.             ** is the overlap variable. If left as is, the
  280.             ** reduction will take one step more than is
  281.             ** necessary. The target list piece is combined
  282.             ** with the last joint piece and processed together.
  283.             **
  284.             ** An example of when this will happen is:
  285.             ** ret(p.a) : p.b = s.b ^ p.c = y.c
  286.             **
  287.             ** Reduction would split this up into
  288.             ** (1) ret (p.a,p.b) : p.c = y.c
  289.             ** (2) ret (p.a) : p.b = s.b
  290.             ** (3) ret (p.a)
  291.             **
  292.             ** Here we are allowing pieces (2) & (3) to be done together
  293.             */
  294.  
  295.             for (cl = joint; cl->linkcomp; cl = cl->linkcomp);
  296.  
  297.             cl->linkcomp = tlpiece;
  298.             joint->nextcomp = 0;
  299.  
  300.             /* switch tl clause to top of complist */
  301.             tmp = joint->clause;
  302.             joint->clause = tlpiece->clause;
  303.             tlpiece->clause = tmp;
  304.         }
  305.     }
  306.  
  307.     if (disjoint)
  308.     {
  309.         ret = xd;
  310.         disjoint->nextcomp = joint ? xj : tlpiece;
  311.     }
  312.  
  313.     return (ret);
  314. }
  315.